# 在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。
# （一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）
#  我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。
#  返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
#  如果无法做到，返回 -1.
#
#  示例 1：
#  输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
# 输出：2
# 解释：
# 图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。
# 如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
#
#  示例 2：
#  输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
# 输出：-1
# 解释：
# 在这种情况下，不可能旋转多米诺牌使一行的值相等。
import collections
from typing import List


class Solution:
    def minDominoRotations2(self, tops: List[int], bottoms: List[int]) -> int:
        """
        贪心算法
        从结果出发，总共有三种情况
            1、不能全同；
            2、可以tops[0]为基准的全同；
            3、可以bottoms[0]为基准的全同；
        具体做法:
            选择第一块多米诺骨牌，它包含两个数字 tops[0] 和 bottoms[0]；
            检查其余的多米诺骨牌中是否出现过 A[0]。如果都出现过，则求出最少的翻转次数，其为将 A[0] 全部翻到 A 和全部翻到 B 中的较少的次数。
            检查其余的多米诺骨牌中是否出现过 B[0]。如果都出现过，则求出最少的翻转次数，其为将 B[0] 全部翻到 A 和全部翻到 B 中的较少的次数。
            如果上述两次检查都失败，则返回 -1。
        :param bottoms:
        :return:
        """
        def check(target) -> int:
            rotateTops, rotaBottoms = 0, 0
            for i in range(len(tops)):
                if tops[i] != target and bottoms[i] != target:  # 上下都不等于target则不可能完成旋转
                    return -1
                elif tops[i] != target:  # 上半部分不等于target则进行旋转
                    rotateTops += 1
                elif bottoms[i] != target:  # 下半部分不等于target则进行旋转
                    rotaBottoms += 1
            return min(rotateTops, rotaBottoms)
        resTop = check(tops[0])
        resBottom = check(bottoms[0])
        if resTop != -1 and resBottom != -1:  # 两种方式都能达到目标，则返回较小值
            return min(resTop, resBottom)
        else:  # 至少一种不能达到目标，则返回较大值
            return max(resTop, resBottom)

    def minDominoRotations1(self, tops: List[int], bottoms: List[int]) -> int:
        counts = [0] * 7  # 用于记录两个数组中去重的统计
        n = len(tops)
        theSame = collections.defaultdict(int)  # 记录上部分和下部分相同的数字(key:数字，vale:出现的次数)
        for i in range(n):
            if tops[i] == bottoms[i]:
                theSame[tops[i]] += 1
                if len(theSame) == 2:  # 出现了两种相同的数字，则不可能完成翻转
                    return -1
            else:
                counts[tops[i]] += 1
                counts[bottoms[i]] += 1

        if len(theSame.keys()) == 1:  # 出现了一种相同的数字
            for k, v in theSame.items():
                countA = sum([1 if i == k else 0 for i in tops])
                countB = sum([1 if i == k else 0 for i in bottoms])
                if countA + countB - v == n:
                    return n - max(countA, countB)
                else:
                    return -1
        else:
            maxCounts = max(counts)
            if maxCounts == n:
                for i in range(7):
                    if counts[i] == maxCounts:
                        countA = sum([1 if j == i else 0 for j in tops])
                        countB = sum([1 if j == i else 0 for j in bottoms])
                        print(countA, countB)
                        return n - max(countA, countB)
            else:
                return -1

    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        return self.minDominoRotations2(tops, bottoms)


if __name__ == "__main__":
    A, B = [2, 1, 2, 4, 2, 2], [5, 2, 6, 2, 3, 2]
    # A = [3, 5, 1, 2, 3]
    # B = [3, 6, 3, 3, 4]
    # A = [1, 2, 3, 4, 6]
    # B = [6, 6, 6, 6, 5]
    print(Solution().minDominoRotations(A, B))
